%---------GALE - SHAPLEY ALGORITHM (Men propose) --------%
% Terminal condition: this code runs until the unmatched agents on proposer
% side have proposed to all agents on the other side

% INPUTS:   men_pref: (Nmen x Nwomen) matrix, where a row is the men's
%                   ordering

%           women_pref: (Nwomen x Nmen) matrix, where a row is the women's ordering

% OUTPUTS: women_partner: a vector of the partner of the reviewer (i.e., women_partner(i)
%                           is the i^th woman's partner (0 if unmatched)


%men_partner 
function [women_partner] = galeshapley_gender_unbalanced(men_pref, women_pref)

[Nmen, Nwomen]=size(men_pref);

men_match = zeros(Nmen,1);
women_suitor = zeros(Nwomen,Nmen);
women_partner = zeros(Nwomen,1);
rank = zeros(Nwomen,Nmen);
men_unmatch_unprop=1;



for i = 1:Nwomen
    for j = 1:Nmen
        for k = 1:Nmen
        if(women_pref(i,k) == j)
            rank(i,j) = k;  % rank(i,j) tells us the order of men j in women i's preferences (i.e., if ordering is 4>1>3>2, then the row of rank is 2,4,3,1)
        end
        end
    end
end


while (men_unmatch_unprop> 0) % if there are unmatched men who have not proposed to all women
    for i = 1:Nmen
        if (men_match(i,1) == 0) && (max(men_pref(i,:))>0) % if men i is unattached and has not proposed to all women
            next = find(men_pref(i,:) > 0, 1); % first non-zero entry in preferences (index of most preferred women men i hasn't yet proposed to)
            women_suitor(men_pref(i,next),i) = i; % (j,i) entry is men i proposing to women j
            men_pref(i,next) = 0;  % now zero out in the preference matrix (so that next time won't propose)
        end
    end
    for i = 1:Nwomen
        for j = 1:Nmen
            if(women_suitor(i,j) ~= 0)  % look at a cell where woman i has men j proposing to her
                if(women_partner(i,1) == 0) % if women i is unattached
                    women_partner(i,1) = women_suitor(i,j); % then her partner is the suitor
                    men_match(j,1) = 1; % and the men is no longer available
                end
                if(women_partner(i,1) ~= 0) % if women i is partnered
                if(rank(i,women_suitor(i,j)) < rank(i,women_partner(i,1))) % if the suitor is preferred (has a lower rank)
                    men_match(women_partner(i,1),1) = 0; % interim partner is now free 
                    women_partner(i,1) = women_suitor(i,j); % suitor turns into partner
                    men_match(j,1) = 1; % men is now matched
                    
                end
                end
            end
        end
    end

    
    men_unmatch_unprop=sum(sum(repmat(1-men_match,1,Nwomen).*men_pref)); % if this is zero, then all men who are unmatched have proposed to all women
end

stablematch = women_partner;





          
        
        
        
        